1. Field of the Invention
The present invention relates to an error correction technique for use in a record reproduction apparatus, a reception apparatus, et cetera, and in particular to an apparatus correcting an error of a data string by using a Reed Solomon code.
2. Description of the Related Art
A Reed Solomon code (e.g., refer to the following non-patent document 1) is used as an error correction code (ECC) for a record reproduction apparatus, such as magnetic disk apparatus, and a telecommunication system.
Non-patent document 1: IMAI, Hideki, “Theory of Coding”, edited by the Institute of Electronics, Information and Communication, pp. 155-175
In an error correction apparatus, a data string input to an ECC decoder is output from a detector. Usually, a single data string as a decoding candidate is input from a detector 11 to an ECC decoder 12 and a decoding is carried out as shown in FIG. 1A. In this case, if the decoding fails, an error cannot be corrected.
Consequently, there is a case of using an apparatus inputting a plurality of data strings to an ECC decoder 22 from a detector 21 as shown in FIG. 1B. In this case, the ECC decoder 22 decodes the respective data strings as candidates, thereby improving a correction capability.
FIG. 1C exemplifies a configuration of the ECC decoder 22 shown in FIG. 1B. The ECC decoder 22 comprises a syndrome calculation unit 41, an error locator polynomial calculation unit 42, a Chien search execution unit 43 and an error value calculation unit 44.
A plurality of data strings output from the detector 21 is once stored in a data storage unit 31, followed by being input to the ECC decoder 22 one by one, in which event it corrects an error included in the data string by the following procedure:
Step 1: the syndrome calculation unit 41 calculates a syndrome polynomial of the data string input to the ECC decoder 22.
Step 2: the error locator polynomial calculation unit 42 calculates an error locator polynomial from the syndrome polynomial. A calculation algorithm of the error locator polynomial uses a Euclid method or a Berlekamp Massey method for instance (e.g., refer to the following non-patent documents 2 and 3):
Non-patent document 2: E. R. Berlekamp, “Algebraic Coding Theory”, McGraw-Hill Book Co., pp. 176-199 and pp. 218-240, New York, 1968
Non-patent document 3: J. L. Massey, “Shift-Register Synthesis and BCH Decoding”, IEEE Transactions on Information Theory, vol. IT-15, pp. 122-127, 1969
Step 3: the Chien search execution unit 43 carries out a Chien search by using the error locator polynomial obtained in the step 2 and determines a position where an error exists on a data string (i.e., an error position).
Step 4: the error value calculation unit 44 corrects an error value at the error position to a correct value.
Then a decode judgment unit 32 checks validity of the corrected data string output from the error value calculation unit 44 and, if the judgment is “invalid”, deciding a failed correction, and instructs the data storage unit 31 to output the next decoding candidate.
Here, a description of a concrete example of an error correction based on the Reed Solomon code by referring to FIGS. 1D through 1H.
A Reed Solomon code of the number of error corrections of t is generated from a generator polynomial of the degree of 2t. Letting a Galois field used for a coding be GF(23) and the number of error corrections t be “1”, and using a primitive element α, then a generator polynomial of a Reed Solomon code can be expressed as follows, for example:
                                                                        G                ⁡                                  (                  x                  )                                            =                                                (                                      x                    -                    1                                    )                                ⁢                                  (                                      x                    -                    α                                    )                                                                                                        =                                                x                  2                                +                                                      α                    3                                    ⁢                  x                                +                α                                                                        (        1        )            
In this case, a three-bit bit string is handled as one symbol, adding a parity string of 2t (=2) symbols to an information string at the ECC decoder. For example, in the case of coding a bit string as shown in FIG. 1D, “001”, “110” and “101” correspond to 1, α5 and α4, respectively, in Galois field expressions. The j-th symbol represents the coefficient of a term of xj in the polynomial of a transmission word string. Therefore, this bit string represents a polynomial x4+α5x3+α4x2.
The ECC decoder divides a polynomial represented by a bit string by the generator polynomial of the expression (1) as shown in FIG. 1E and adds a parity string representing the resultant remainder polynomial α4x+α4 to the bit string. In this remainder polynomial, coefficients of terms of the first and zeroth order of x are both α4, and therefore the parity string as shown in FIG. 1F is added, thus a transmission word string constituted by five symbols being generated.
When this transmission word string is recorded in a magnetic disk and is read therefrom, a reception word string including an error may possibly be input to the ECC decoder 22 as shown in FIG. 1G. A reception word polynomial represented by the reception word string is as follows:Y(x)=αx4+α5x3+α4x2+α4x+α4  (2)
In this case, the syndrome calculation unit 41 calculates a syndrome polynomial by the following expressions:S(x)=s1+s2x s1=Y(1)s2=Y(α)  (3)
The syndrome si (where i=1, 2, . . . , 2t) is a value obtained by substituting the i-th root of a generator polynomial G(x) for the reception word polynomial Y(x), and the syndrome polynomial S(x) is a polynomial having the syndrome si as the coefficient of a term of xi-1. If an error is not included in the reception word string, all of the si becomes zero.
Then, the error locator polynomial calculation unit 42 calculates, from the syndrome polynomial S(x), an error locator polynomial C(x) as follows:C(x)=1+α−4x  (4)
Then, the Chien search execution unit 43 calculates values of C(αj) (where j=0, 1, 2, 3, 4) by using the error locator polynomial C(x) and outputs a position j where the C(αj)=0 as an error position. In this example, as C(α4)=1+α−4*α4=0, it is found that the fourth symbol has an error.
Then, the error value calculation unit 44 calculates a correct value of the fourth symbol by a predetermined algorithm by using the syndrome polynomial S(x) and error locator polynomial C(x), and corrects the bit string. A correct value “1” is obtained in this event, and the fourth symbol in the reception word string is accordingly changed from α to “1” as shown in FIG. 1H.
A Reed Solomon code with t=20 is sometimes used for a magnetic disk, while in an ECC coder, a 40-symbol parity string is generated and inserted in front of one sector bit string as shown in FIG. 1I, in which case, the syndrome polynomial S(x) and error locator polynomial C(x) are for example as follows:S(x)=s1+s2x+ . . . +s40x39  (5)C(x)=1+x+α2x2+ . . . +α35x8  (6)
The above described conventional ECC decoder is faced with the following problems:
An actual reception word string is far longer than five symbols, making the degree of a reception word polynomial Y(x) large. Consequently, the calculation of the syndrome polynomial S(x) and a calculation volume of a Chien search become enormous, thereby taking a long time for a decoding process.
Meanwhile, the configuration shown by FIG. 1C judges a success or failure of a decoding on the output side of the ECC decoder, and therefore a series of a decoding process is carried out even if a correction has failed due to a certain decoding candidate containing errors exceeding a correction capability of the ECC decoder, thus reducing efficiency. Accordingly desired is a method for judging, in earlier stage, whether or not a decoding of a candidate data string is failed and proceeding to a decoding of the next candidate quickly if a failure is discovered.